
public class Wu_48 {
    public static void main(String[] args) {
        System.out.println("###################LinkList###################");
        LinkList l=new LinkList();
        l.insert(new Node(1));
        l.insert(new Node(2));
        l.insert(new Node(3));
        System.out.println(l);
        l.delete(2);
        System.out.println(l);
        System.out.println("###################Stack by LinkList#####################");
        Stack s=new Stack();
        for(int i=1;i<=5;i++){
            s.push(i);
        }
        while(!s.isEmpty()){
            try {
                System.out.println(s.pop());
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
        System.out.println("##########################Queue by LinkList############################");
       Queue q=new Queue();
        for(int i=1;i<=5;i++){
            q.enqueue(i);
        }
        while(!q.isEmpty()) {
            try {
                System.out.println(q.dequeue());
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
    }
}
class Queue{
    LinkList l;
    public Queue(){
        this.l=new LinkList();
    }
    void enqueue(int key){
        l.insert(new Node(key));
    }
    int dequeue() throws Exception{
        if(isEmpty()){
            throw new Exception("underflow!");
        }else{
            int s=l.nil.prev.key;
            l.delete(s);
            return s;
        }
    }
    boolean isEmpty(){
        return l.isEmpty();
    }
}
class Stack{
    LinkList l;
    public Stack(){
        this.l=new LinkList();
    }
    void push(int n){
       l.insert(new Node(n));
    }
    int pop() throws Exception{
        if(isEmpty()){
            throw new Exception("underflow!");
        }else{
            int x=l.nil.next.key;
            l.delete(x);
            return x;
        }
    }
    boolean isEmpty(){
        return l.isEmpty();
    }
}
class LinkList{
    Node nil;
    public LinkList(){
        nil=new Node(-1);
        nil.next=nil.prev=nil;
    }
    // add a new element need to build four links
    void insert(Node n){
        //build the link which is at the rear firstly
        //supposed that nil.next=a
        n.next=nil.next;
        nil.next.prev=n;
        //if build the link which is nil.next=n,which will cover nil.next=a
        nil.next=n;
        n.prev=nil;
    }
    //delete an element need to build two new links
    //before deleting an element ,we need to know if the element is in this LinkList
    void delete(int key)
    {
        Node x=search(key);
        if(x != nil){
            x.prev.next=x.next;
            x.next.prev=x.prev;
        }
    }
    Node search(int key){
        Node x=nil.next;
        while(x != nil && x.key !=key){
            x=x.next;
        }
        return x;
    }
    public String toString(){
        Node x=nil.next;
        if(x!= nil) {
            String s =" ";
            while(x != nil) {
                s += x.key + " ";
                x = x.next;
            }
            return s;
        }else{
            return null;
        }

    }
    boolean isEmpty(){
        return nil.next==nil;
    }
}

class Node{
    int key;
    Node prev;
    Node next;
    public Node(int key){
        this.key =key;
        prev=next=null;
    }
}